/*
 * @Descripttion: 
 * @version: 
 * @Author: lily
 * @Date: 2021-05-07 10:07:37
 * @LastEditors: lily
 * @LastEditTime: 2021-05-07 11:13:53
 */
/*
 * @lc app=leetcode.cn id=72 lang=javascript
 *
 * [72] 编辑距离
 */

// @lc code=start
/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */

//  思想：动态规划
//  dp[i][j]表示word1的前i到word前j的编辑距离
//  在word1删除等价于在word2插入，前面的比较过了因此比较两者末尾
//  状态转移方程: 分别看增、删、改的最小值
//  1.word1[i] = word2[j]  当前字母相同 看上一次比对
//  dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j] + 1, dp[i][j - 1] + 1)
//  1.word1[i] != word2[j]  当前字母不同
//  dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1

//  复杂度：O(mn) O(mn)

var minDistance = function (word1, word2) {
    const n = word1.length + 1, m = word2.length + 1
    let dp = Array.from(new Array(n), () => new Array(m).fill(0))
    //  设置初始值
    for (let i = 0; i < n; i++) {
        dp[i][0] = i
    }
    for (let j = 0; j < m; j++) {
        dp[0][j] = j
    }

    //  填表
    for (let i = 1; i < n; i++) {
        for (let j = 1; j < m; j++) {
            if (word1[i - 1] === word2[j - 1]) {
                dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j] + 1, dp[i][j - 1] + 1)
            } else {
                dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
            }
        }

    }


    return dp[n - 1][m - 1]
};
// @lc code=end

console.log(minDistance('intention', 'execution'));